#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), m = 0;
        for (auto i : nums) m += i;
        int t = m + target;
        if (t % 2 || t < 0) return 0;
        t /= 2;
        vector<int> dp(t + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = t; j >= nums[i - 1]; j--)
                dp[j] += dp[j - nums[i - 1]];
        return dp[t];
    }
};

class Solution {
public:
    int aim, ret = 0;
    int findTargetSumWays(vector<int>& nums, int target) {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int path)
    {
        if (pos == nums.size())
        {
            if (path == aim) ret++;
            return;
        }

        dfs(nums, pos + 1, path + nums[pos]);
        dfs(nums, pos + 1, path - nums[pos]);
    }
};